package crazy;

public class QuickSort
{

	public static void main(String[] args)
	{
		DataWrap[] data = { new DataWrap(21, ""), new DataWrap(30, ""),
				new DataWrap(49, ""), new DataWrap(30, "*"),
				new DataWrap(16, ""), new DataWrap(9, "") };
		
		System.out.println("before sorting-->"+java.util.Arrays.toString(data));
		quickSort(data);
		System.out.println("after sorting-->"+java.util.Arrays.toString(data));
	}

	public static void quickSort(DataWrap[] data)
	{
		subSort(data, 0, data.length-1);
	}
	
	public static void subSort(DataWrap[] data, int start, int end)
	{
		if (start<end)
		{
			DataWrap base = data[start];
			int i = start;
			int j = end + 1;
			while (true)
			{
				while (i<end && data[++i].compareTo(base)<=0);
				while (j>start && data[--j].compareTo(base)>=0);
				if(i<j)
				{
					swap(data, i, j);
				}
				else 
				{
					break;
				}
			}
			swap(data, start, j);
			subSort(data, start, j-1);
			subSort(data, j+1, end);
		}
	}
	
	public static void  swap(DataWrap[] data, int i, int j)
	{
		DataWrap tmp = data[i];
		data[i] = data[j];
		data[j] = tmp;
	}
	
}
